The approaches described in this section could be pursued, but are not necessarily approaches that previously have been conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
Computers may communicate with each other through a network by sending data packets to each other. While there are numerous protocols according to which one computer may address a data packet to another computer, a protocol commonly used for this purpose is Internet Protocol (IP). Typically, a data packet that is structured according to IP (an “IP data packet”) contains a source IP address and a destination IP address. By examining a destination IP address contained in an IP data packet, a network device can determine the identity of a computer to which the IP data packet ultimately should be transmitted.
The computer that originates an IP data packet (the “originating computer”) is often not directly connected to the computer for which the IP data packet is destined (the “destination computer”). The originating computer and the destination computer often transmit IP data packets through several interconnected intermediate network devices, such as network routers. Each router maintains a routing table that contains information that the router uses to select one of potentially several directly connected network devices to which the router should forward an IP data packet. Because each such directly connected network device is connected to a router port, the router selects one of potentially several ports through which to forward the packet.
By communicating the information in their routing tables to other routers and updating their routing tables based on information received from other routers, routers can attempt to “learn” from each other the network routes, or paths, from different sources to different destinations. Routers communicate such routing table information using a routing protocol. Some examples of routing protocols are distance vector protocols, such as Routing Information Protocol (RIP), and link state protocols, such as Open Shortest Path First (OSPF) protocol. RIP is described in the Internet Engineering Task Force (IETF) Request For Comments (RFC) 1058. OSPF is described in IETF RFC 1247.
Di Caro, G. and Dorigo, M. (1998) “Ant Net: Distributed Stigmergetic Control for Communications Networks,” Journal of Artificial Intelligence Research (JAIR), 9:317-365, describes a theoretical probabilistic routing approach. This “Ant Net” approach is modeled after the behavior of ants, which determine a best path to a destination by stochastically selecting between paths based on pheromones deposited on such paths by other ants. As more ants follow a particular path, more pheromones are deposited on the particular path relative to other paths. Because shorter paths tend to be traversed more quickly, shorter paths tend to accumulate more pheromone than longer paths. As more pheromones are deposited on a particular path, more ants are likely to select the particular path over other paths. However, because the ants' behavior is probabilistic, there is always a chance that an ant may select a path other than the path on which the most pheromones have been deposited, thus increasing the probability that other ants will also select that other path.
By incorporating a similar element of chance, probabilistic routing approaches have some advantages over distance vector protocols and link state protocols. Distance vector protocols and link state protocols do not provide for alternative paths between an originating computer and a destination computer. As a result, these protocols route all traffic between an originating computer and a destination computer over the same path, even when the traffic load on that path is high, and even when other unused paths between the originating computer and the destination computer are available. In contrast, probabilistic routing approaches may send portions of such traffic over multiple different paths, thereby balancing the traffic load over the paths.
Probabilistic routing approaches also recover more quickly from link failures. Because distance vector protocols and link state protocols only provide for one path between an originating computer and a destination computer at a time, the failure of a link on that path causes significant delay while these protocols attempt to re-route the traffic that formerly passed through the failed link. In contrast, probabilistic routing approaches quickly adapt to link failures as the use of alternative paths is reinforced and the continued use of broken paths is undermined.
When a new and better path between a source computer and a destination computer becomes available, probabilistic routing approaches tend to discover and make use of the new path. In contrast, distance vector protocols and link state protocols tend to ignore new paths in favor of established paths, even when the new paths are better than the established paths.
However, there are a few drawbacks to probabilistic routing approaches. When the load on a best path between an originating computer and a destination computer is low, there is little benefit in sending traffic over alternative paths. Indeed, concurrently sending portions of traffic over multiple different paths may cause packets to arrive at a destination computer out of order, which can require re-transmission of packets. Additionally, previous probabilistic routing approaches could not guarantee that paths would be loop-free.
Based on the foregoing, there is a clear need for a method of updating network routing information so that data packets are routed in a manner that lacks the disadvantages inherent in distance vector protocols, link state protocols, and probabilistic routing approaches.
More specifically, there is a need for a method of updating network routing information so that data packets are routed in a manner that does not always restrict traffic to a single path, and in a manner that reduces the routing of traffic over suboptimal paths.